package DoExercise.HSP_ZCY.A015_暴力递归;

/**
 * N皇后问题是指在N*N的棋盘上要摆N个皇后，
 * 要求任何两个皇后不同行、不同列， 也不在同一条斜线上
 * <p>
 * 给定一个整数n，返回n皇后的摆法有多少种。  n=1，返回1
 * n=2或3，2皇后和3皇后问题无论怎么摆都不行，返回0
 * n=8，返回92
 */
public class Code09_N皇后问题
{
    public static void main(String[] args)
    {
        int n = 8;
        
        long start = System.currentTimeMillis();
        System.out.println(num2(n));
        long end = System.currentTimeMillis();
        System.out.println("cost time: " + (end - start) + "ms");
        
        start = System.currentTimeMillis();
        System.out.println(num1(n));
        end = System.currentTimeMillis();
        System.out.println("cost time: " + (end - start) + "ms");
    }
    
    public static int num1(int n)
    {
        if (n < 1)
        {
            return 0;
        }
        int[] record = new int[n]; //record[3] = 8 表示第4行的皇后在第4行的第8个位置
        return process1(0, record, n);
    }
    
    /**
     * 潜台词：record[0..i-1]的皇后，任何两个皇后一定都不共行、不共列，不共斜线
     * 目前来到了第i行
     * record[0..i-1]表示之前的行，放了的皇后位置
     * n代表整体一共有多少行
     * 返回值是，摆完所有的皇后，合理的摆法有多少种
     *
     * @param i
     * @param record 之前皇后的所有位置
     * @param n      皇后数量
     * @return
     */
    public static int process1(int i, int[] record, int n)
    {
        if (i == n)
        { // 终止行，上面已经摆好的状态
            return 1;
        }
        int res = 0;
        for (int j = 0; j < n; j++)//循环列
        {
            if (isValid(record, i, j))
            {
                record[i] = j;
                res += process1(i + 1, record, n);
            }
        }
        return res;
    }
    
    /**
     * record[0..i-1]你需要看，record[i...]不需要看
     * 返回i行皇后，放在了j列，是否有效
     *
     * @param record
     * @param i      当前是第几个皇后
     * @param j      当前行的皇后放在第几列
     * @return
     */
    public static boolean isValid(int[] record, int i, int j)
    {
        for (int k = 0; k < i; k++)
        {   //j == record[k] 列冲突
            //Math.abs(record[k] - j) == Math.abs(i - k) 斜线冲突，record[k]之前皇后的行数  k之前皇后的列数  j当前皇后的行数  i当前皇后的列数
            //record 本身已经保证 行不冲突了
            if (j == record[k] || Math.abs(record[k] - j) == Math.abs(i - k))
            {
                return false;
            }
        }
        return true;
    }
    
    
    /**
     * N皇后问题第二种实现，请不要超过32皇后问题
     *
     * @param n
     * @return
     */
    public static int num2(int n)
    {
        if (n < 1 || n > 32)
        {
            return 0;
        }
        int limit = n == 32 ? -1 : (1 << n) - 1;
        return process2(limit, 0, 0, 0);
    }
    
    /**
     * colLim 列的限制，1的位置不能放皇后，0的位置可以
     * leftDiaLim 左斜线的限制，1的位置不能放皇后，0的位置可以
     * rightDiaLim 右斜线的限制，1的位置不能放皇后，0的位置可以
     * <p>
     * 复杂度依旧是O(Math.pow(N,N))
     * 位运算只是加速了常数时间
     *
     * @param limit       问题的规模 确定几皇后问题
     * @param colLim      列的限制 1不能放皇后 0可以放皇后
     * @param leftDiaLim  左对角线限制
     * @param rightDiaLim 右对角线限制
     * @return
     */
    public static int process2(int limit, int colLim, int leftDiaLim, int rightDiaLim)
    {
        if (colLim == limit)//当列上已经点满皇后了，和limit相等
        { // base case
            return 1;
        }
        // 所有候选皇后的位置，都在pos上
        int pos = limit & (~(colLim | leftDiaLim | rightDiaLim));//limit & 是截掉左边超限的1
        int mostRightOne = 0;
        int res = 0;
        while (pos != 0)
        {
            mostRightOne = pos & (~pos + 1);//每次不断提出最右侧的1
            pos ^= mostRightOne;//截掉右侧的1，表示当前点的皇后的位置
            res += process2(limit, colLim | mostRightOne, (leftDiaLim | mostRightOne) << 1, (rightDiaLim | mostRightOne) >>> 1);
        }
        return res;
    }
}
